import java.util.PriorityQueue;

/**
 * @author hewei
 * @version 1.0
 * @description: 1642. 可以到达的最远建筑
 * @date 2022/11/22 15:05
 */

public class FurthestBuilding {

    public static void main(String[] args) {
        int[] nums = {1,5,1,2,3,4};
        System.out.println(new FurthestBuilding().furthestBuilding(nums, 4, 1));
    }

    public int furthestBuilding1(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        int index = 1;
        while (index < heights.length && (bricks >= 0 || ladders >= 0 || heights[index] <= heights[index - 1])) {
            if (heights[index] <= heights[index - 1]) {
                ++index;
            } else if (bricks >= 0) {
                int temp = heights[index] - heights[index - 1];
                if (bricks >= temp) {
                    ++index;
                }
                bricks -= temp;
                heap.offer(temp);
            } else {
                while (!heap.isEmpty() && ladders > 0 && bricks < 0) {
                    bricks += heap.poll();
                    --ladders;
                }
                if (bricks < 0) {
                    return --index;
                } else {
                    ++index;
                }
            }
        }
        if (bricks < 0) {
            return --index;
        } else {
            return Math.min(heights.length - 1, index);
        }
    }

    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int n = heights.length;
        for (int i = 1; i < n; i++) {
            int delta = heights[i] - heights[i - 1];
            if (delta > 0) {
                heap.add(delta);
                if (heap.size() > ladders) {
                    bricks -= heap.poll();
                }
            }
            if (bricks < 0) {
                return i - 1;
            }
        }
        return n - 1;
    }
}
